package main.Q1401_1500;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class Q1481_1490 {
    public static void main(String[] args) {
        System.out.println("Question1481：");
        System.out.println("Question1482：制作m束花所需的最少天数");
        System.out.println("Question1483：");
        System.out.println("Question1484：");
        System.out.println("Question1485：");
        System.out.println("Question1486：");
        System.out.println("Question1487：");
        System.out.println("Question1488：避免洪水泛滥");
        System.out.println("Question1489：");
        System.out.println("Question1490：");
    }
}

class Question1482{
    public boolean process(int[] bloomDay,int m,int k,int day){
        int count=0;
        for (int i=0;i< bloomDay.length;i++){
            if (bloomDay[i]<=day) count++;
            else count=0;
            if (count==k) {
                count=0;
                m--;
            }
        }
        if (m<=0) return true;
        else return false;
    }
    public int minDays(int[] bloomDay, int m, int k) {
        int left=1,right=(int)1e9;
        if ((long)m*(long) k> bloomDay.length) return -1;//花不够
        while (left<right){
            int mid=left+(right-left)/2;
            if (process(bloomDay,m,k,mid)) right=mid;
            else left=mid+1;
        }
        return left;
    }
}

class Question1488{
    public int[] avoidFlood(int[] rains) {
        int[] ans = new int[rains.length];
        Arrays.fill(ans, 1);
        Map<Integer, Integer> water = new HashMap<>();
        TreeSet<Integer> zero = new TreeSet<>();
        for(int i = 0; i < rains.length; ++i){
            int rain = rains[i];
            if(rain == 0){//晴天，存下标
                zero.add(i);
                continue;
            }
            if(water.containsKey(rain)){//下雨天，且这个湖泊已经下过雨了
                Integer r = zero.higher(water.get(rain));//找到之前一次下雨的下标所对应的下一个晴天下标
                if(r == null) return new int[]{};//如果没有满足要求的晴天下标，返回空数组
                ans[r] = rain;//清空的湖泊下标
                zero.remove(r);//移除已经使用过的晴天
            }
            water.put(rain, i);//存放下雨的湖泊
            ans[i] = -1;//下雨不能操作
        }
        return ans;
    }
}